package MyLinkedList;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class MyLinkedList<E> implements List<E>  {
	private final MyNode<E> _root = new MyNode<E>(null);
	private int _size;
	private Object _footprint;
	
	
	
	private static class MyNode<E> {
		private E _value;
		private MyNode<E> _next = null;		
		
		protected MyNode(E _value) {
			super();
			this._value = _value;
		}
		
		protected MyNode(E _value, MyNode<E> _next) {
			this(_value);
			this._next = _next;
		}
	}
	
	public MyLinkedList() {
		super();
		this._size = 0;
	}


	private void checkIndexBounds(int index) {
		if (index < 0 || index >= _size) throw new IndexOutOfBoundsException();
	}
	
	private MyNode<E> getNodeAt(int index) {
		MyNode<E> cur = null;
		
		for (cur = _root; index != 0; --index, cur = cur._next);
		
		return cur;
	}

	@Override
	public void add(int index, E element) {
		if (index < 0 || index >= _size+1) throw new IndexOutOfBoundsException();
		
		MyNode<E> cur = getNodeAt(index);
		MyNode<E> newNode = new MyNode<E>(element, cur._next);
		cur._next = newNode;
		
		_footprint = new Object();
		
		++_size;		
	}



	@Override
	public E get(int index) {
		checkIndexBounds(index);
		
		return getNodeAt(index)._next._value;
	}


	@Override
	public E remove(int index) {
		checkIndexBounds(index);
		
		MyNode<E> pred = getNodeAt(index);
		MyNode<E> oldNode = pred._next;
		
		pred._next = pred._next._next;
		
		oldNode._next = null;
		
		--_size;
		_footprint = new Object();
		
		return oldNode._value;
	}



	@Override
	public E set(int index, E element) {
		checkIndexBounds(index);
		
		MyNode<E> node = getNodeAt(index)._next;
		E oldValue = node._value;
		node._value = element;
		
		return oldValue;
	}



	@Override
	public int size() {
		return _size;
	}


	@Override
	public boolean isEmpty() {
		return _size == 0;
	}
	
	
	@Override
	public Iterator<E> iterator() {
		return new Iterator<E>() {
			private MyNode<E> _cursor = _root;
			private MyNode<E> _pred;
			private boolean _nextCalled = false;
			private Object _myFootPrint = _footprint;

			@Override
			public boolean hasNext() {
				return _cursor._next != null;
			}
			
			private void checkModified() {
				if (_footprint != _myFootPrint)
					throw new ConcurrentModificationException();
			}

			@Override
			public E next() {
				if (!hasNext()) throw new NoSuchElementException();
				checkModified();
				
				E toRet = _cursor._next._value;
				_pred = _cursor;
				_cursor = _cursor._next;
				
				_nextCalled = true;
				
				return toRet;
			}

			@Override
			public void remove() {
				if (!_nextCalled)
					throw new IllegalStateException();
				checkModified();
				
				_pred._next = _cursor._next;
				--_size;
				
				_footprint = _myFootPrint = new Object();
				
				_nextCalled = false;
			}
		};
	}
}
